# encoding:utf-8

import sys
import csv
import copy

# MAP 文件包含要素
# ①每个形状可移动的方向（允许限制方向，上下左右，行动模式：步长 或 到底），和形状位置（二元坐标）
# ②特殊形状：边界（二元坐标）
# ③求解目标：允许包括多个目标，每个目标格式：起始位置（二元坐标），目标位置（二元坐标）
#
# 示例图：经典华容道
# ■■■■■■    ■边界
# ■▲○○△■    ▲张飞 ○曹操 △赵云
# ■▲○○△■
# ■◆★★◇■    ◆黄忠 ★关羽 ◇马超
# ■◆□◎◇■    □卒 ◎卒
# ■☆  ●■    ☆卒 ●卒
# ■■■■■■
# 示例【张飞】：s:[[1,1],[2,1],[3,1],[4,1]]:[[2,2],[3,2]]
# 含义解析：(用:分割，下同)
# s为一行的开头，s表示该行数据为形状描述
# 第一组[x,y]：x代表可移动方向，1234分别对应上下左右；y代表每次步长，0表示不能移动，-1表示移动到撞上东西为止。补充：实际上0步长可以直接不写这个方向。
# 第二组[x,y]：在以1开始计数的格子棋盘上，所处的坐标为止，x代表行，y代表列（参考Excel R1C1样式）
# 以下为全部的11种图形描述（包括了边界）
# s:[]:[[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[2,1],[2,6],[3,1],[3,6],[4,1],[4,6],[5,1],[5,6],[6,1],[6,6],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[2,2],[3,2]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[2,3],[2,4],[3,3],[3,4]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[2,5],[3,5]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[4,2],[5,2]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[4,3],[4,4]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[4,5],[5,5]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[5,3]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[5,4]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[6,2]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[6,5]]
#
# 求解目标，依旧以经典华容道为例，最终目标如下
# ■■■■■■
# ■    ■
# ■    ■
# ■    ■
# ■ ○○ ■    ○曹操
# ■ ○○ ■
# ■■■■■■
# 目标示例：t:[[2,3],[5,3]]
# 含义解析：
# t为一行的开头，表示该行数据为目标描述，永远只有一行
# 最外层[]不解释，中间层[]代表一个目标，可以存在多个不同目标（用:隔开），虽然经典华容道只有一个
# 内层[x1,y1],[x2,y2]，表示需要将原来处于坐标[x1,y1]的形状，移动到[x2,y2]，可以用形状内的任意一点作为对象
# 以下为经典华容道的目标示例（全部为等效行，只选择其中一行即可）
# t:[[[2,3],[5,3]]]
# t:[[[2,4],[5,4]]]
# t:[[[3,3],[6,3]]]
# t:[[2,3],[5,3]]:[[2,4],[5,4]]:[[3,3],[6,3]]:[[3,4],[6,4]]
#
# 综上，完整的map文件包含下述内容（顺序无关）
# s:[]:[[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[2,1],[2,6],[3,1],[3,6],[4,1],[4,6],[5,1],[5,6],[6,1],[6,6],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[2,2],[3,2]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[2,3],[2,4],[3,3],[3,4]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[2,5],[3,5]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[4,2],[5,2]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[4,3],[4,4]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[4,5],[5,5]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[5,3]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[5,4]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[6,2]]
# s:[[1,1],[2,1],[3,1],[4,1]]:[[6,5]]
# t:[[2,3],[5,3]]

# 读取MAP文件并解析到序列中【形状、目标】
# TODO：MAP文件改为调用系统选择框
# TODO：自动解析文件encoding
target_count = 0
shape_count = 0
target = []
shape = []
map_file = open('in\\map.txt', mode='r', encoding='utf-8')
map_reader = csv.reader(map_file, delimiter=':')
for row in map_reader:
    if row[0] == 's':
        # 格式检查
        if len(row) != 3:
            print('形状行格式错误')
            sys.exit(1)
        # 填充形状序列
        shape_count += 1
        shape.append([])
        shape[-1].append(shape_count)
        shape[-1].append(eval(row[1]))
        shape[-1].append(eval(row[2]))
    elif row[0] == 't':
        # 格式检查
        target_count += 1
        # 记录目标行
        for i in range(1, len(row)):
            target.append(eval(row[i]))
    else:
        # 格式检查
        print("不可识别的行")
        sys.exit(1)
map_file.close()
# 格式检查
if target_count != 1:
    print("目标行数不为1")
    sys.exit(1)

# check point - 打印解析形状
print('共 {} 个形状'.format(len(shape)))
for i in shape:
    print(i)
print('')
print('共 {} 个目标'.format(len(target)))
for i in target:
    print(i)
print('')

# 从【形状】列表中生成MAP
row = 0
column = 0
for i in shape:
    for j in i[2]:
        row = max(row, j[0])
        column = max(column, j[1])
map_list = [[0 for x in range(column)] for x in range(row)]
for i in shape:
    for j in i[2]:
        map_list[j[0] - 1][j[1] - 1] = i[0]

# 目标坐标修正
target_init_shape = copy.deepcopy(target)
target_init_shape = [x[0] for x in target_init_shape]
for i in range(len(target)):
    target[i][0][0] -= 1
    target[i][0][1] -= 1
    target[i][1][0] -= 1
    target[i][1][1] -= 1


# 打印map图形
def print_map(t):
    for i in t:
        print(i)
    print('')


# check point - 打印map
print('当前MAP')
print_map(map_list)
print('')

# 比较目标当前位置与最终位置
target_init = [x[0] for x in target]
target_final = [x[1] for x in target]


# 检查目标达成
def check_target(t):
    if t == target_final:
        return True
    else:
        return False


# 广搜核心程序
# 广搜数据结构：
# 本级指针(index),[上级指针,map,目标位置,总步数,|简化MAP|,[图形编号,移动方向]]
# 广搜思路：
# 1 尝试所有可能移动：每个shape每个方向
#   1.1 检查是否达成目标
#       达成：结束，回溯指针出解
#   1.2 检查是否与历史重复
# 2 与历史不重复，列表+1
# 3 尝试下一个


# 检查所有方向上可移动的步数
def cal_move(sh, map_d):
    step_list = []
    for i in sh[1]:
        if i[0] == 1:  # 向上移动
            max_move = -1
            for r in range(len(map_d)):
                for c in range(len(map_d[0])):
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, r + 1):
                            if map_d[r - m][c] == 0 or map_d[r - m][c] == sh[0]:
                                e_move = m
                            else:
                                break
                        if e_move == 0:
                            max_move = 0
                            break
                        else:
                            if max_move == -1:
                                max_move = e_move
                            else:
                                max_move = min(max_move, e_move)
                if max_move == 0:
                    break
            if i[1] == -1:
                step_list.append([i[0], max_move])
            else:
                step_list.append([i[0], min(i[1], max_move)])
        elif i[0] == 2:  # 向下移动
            max_move = -1
            for r in range(len(map_d)):
                for c in range(len(map_d[0])):
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, len(map_d) - r):
                            if map_d[r + m][c] == 0 or map_d[r + m][c] == sh[0]:
                                e_move = m
                            else:
                                break
                        if e_move == 0:
                            max_move = 0
                            break
                        else:
                            if max_move == -1:
                                max_move = e_move
                            else:
                                max_move = min(max_move, e_move)
                if max_move == 0:
                    break
            if i[1] == -1:
                step_list.append([i[0], max_move])
            else:
                step_list.append([i[0], min(i[1], max_move)])
        elif i[0] == 3:  # 向左移动
            max_move = -1
            for r in range(len(map_d)):
                for c in range(len(map_d[0])):
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, c + 1):
                            if map_d[r][c - m] == 0 or map_d[r][c - m] == sh[0]:
                                e_move = m
                            else:
                                break
                        if e_move == 0:
                            max_move = 0
                            break
                        else:
                            if max_move == -1:
                                max_move = e_move
                            else:
                                max_move = min(max_move, e_move)
                if max_move == 0:
                    break
            if i[1] == -1:
                step_list.append([i[0], max_move])
            else:
                step_list.append([i[0], min(i[1], max_move)])
        elif i[0] == 4:  # 向右移动
            max_move = -1
            for r in range(len(map_d)):
                for c in range(len(map_d[0])):
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, len(map_d[0]) - c):
                            if map_d[r][c + m] == 0 or map_d[r][c + m] == sh[0]:
                                e_move = m
                            else:
                                break
                        if e_move == 0:
                            max_move = 0
                            break
                        else:
                            if max_move == -1:
                                max_move = e_move
                            else:
                                max_move = min(max_move, e_move)
                if max_move == 0:
                    break
            if i[1] == -1:
                step_list.append([i[0], max_move])
            else:
                step_list.append([i[0], min(i[1], max_move)])
    return step_list


# 检查是否与历史重复
# 排除相同图形
def simple_shape(t):
    # 最简化图形
    t_copy = copy.deepcopy(t)
    r_s = t_copy[0][0]
    c_s = t_copy[0][1]
    for i in t_copy[1:]:
        r_s = min(r_s, i[0])
        c_s = min(c_s, i[1])
    for i in t_copy:
        i[0] = i[0] - r_s
        i[1] = i[1] - c_s
    return t_copy


# 记录所有图形对应关系
# 数据结构：[最简化图形,图形编号,[相同图形编号]]
shape_same = []
for i in shape:
    p = False  # 是否目标图形?
    for j in target_init_shape:
        if j in i[2]:
            p = True
            break
    if p:
        continue
    simp_s = simple_shape(i[2])
    p = True  # 不存在相似图形？
    for j in shape_same:
        if simp_s == j[0]:
            p = False  # 找到追加相似
            j[2].append(i[0])
            break
    if p:  # 没找到追加新图形
        shape_same.append([simp_s, i[0], []])


# for i in shape: # 目标图形不需要放进去
#     for j in target_init_shape:
#         if j in i[2]:
#             shape_same.append(['target', i[0], []])
#             break


# 检查是否与历史重复(版本3)
def check_history(t):  # 有重复返回False
    for i in map_history:
        if t == i[4]:
            return False
    return True


def simp_map(t):
    # 简化MAP-相同图形处理
    t_c = copy.deepcopy(t)
    for a in t_c:
        for b in range(len(a)):
            for c in shape_same:
                if a[b] in c[2]:
                    a[b] = c[1]
                    break
    return t_c


# 广搜数据结构：
# 本级指针(index),[上级指针,map,目标位置,总步数,|简化MAP|,[图形编号,移动方向、步数]]
map_history = [[-1, map_list, target_init, 0, simp_map(map_list), [0, '']]]

direction_dic = {1: '上', 2: '下', 3: '左', 4: '右'}

# 求解优化-shape排序:优先移动目标图形，然后移动大图形，然后小图形
shape.sort(key=lambda sh: len(sh[2]), reverse=True)
for i in range(len(shape)):
    for j in target_init_shape:
        if j in shape[i][2]:
            shape.insert(0, shape[i])
            shape.pop(i + 1)
            continue

# 求解核心
current = 0
while (current < len(map_history)) and (not check_target(map_history[current][2])):
    if current % 500 == 0:
        print('第 {} 次循环，第 {} 步'.format(current, map_history[current][3]))
    # todo 测试
    # print('第 {} 次循环，第 {} 步，父节点 {}'.format(current, map_history[current][3], map_history[current][0]))
    # print_map(map_history[current][1])
    # if current == 5548:
    #     print_map(map_history)
    #     sys.exit(0)
    # 以上部分为测试
    for i in shape:  # 每个形状
        steps = cal_move(i, map_history[current][1])
        for j in steps:  # 每个方向
            if j[0] == 1 and j[1] != 0:  # 向上移动
                map_copy = copy.deepcopy(map_history[current][1])
                target_copy = copy.deepcopy(map_history[current][2])
                for c in range(len(map_copy[0])):
                    for r in range(len(map_copy)):
                        if map_copy[r][c] == i[0]:
                            map_copy[r - j[1]][c] = i[0]
                            map_copy[r][c] = 0
                            for tn in range(len(target_copy)):
                                if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                    target_copy[tn][0] -= j[1]
                # 检查条件：
                # ①是否直接达成目标
                # if check_target(target_copy):
                #     print('已经找到满足条件的解，需要打印')
                #     pass
                #     exit(0)
                # ②不能与历史位置产生重复
                map_copy_s = simp_map(map_copy)
                if check_history(map_copy_s):
                    map_history.append(
                        [current, map_copy, target_copy, map_history[current][3] + 1, map_copy_s,
                         [i[0], direction_dic[j[0]] + str(j[1])]])
            elif j[0] == 2 and j[1] != 0:  # 向下移动
                map_copy = copy.deepcopy(map_history[current][1])
                target_copy = copy.deepcopy(map_history[current][2])
                for c in range(len(map_copy[0])):
                    for r in range(len(map_copy) - 1, -1, -1):
                        if map_copy[r][c] == i[0]:
                            map_copy[r + j[1]][c] = i[0]
                            map_copy[r][c] = 0
                            for tn in range(len(target_copy)):
                                if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                    target_copy[tn][0] += j[1]
                # 检查条件：
                # ①是否直接达成目标
                # if check_target(target_copy):
                #     print('已经找到满足条件的解，需要打印')
                #     pass
                #     exit(0)
                # ②不能与历史位置产生重复
                map_copy_s = simp_map(map_copy)
                if check_history(map_copy_s):
                    map_history.append(
                        [current, map_copy, target_copy, map_history[current][3] + 1, map_copy_s,
                         [i[0], direction_dic[j[0]] + str(j[1])]])
            elif j[0] == 3 and j[1] != 0:  # 向左移动
                map_copy = copy.deepcopy(map_history[current][1])
                target_copy = copy.deepcopy(map_history[current][2])
                for r in range(len(map_copy)):
                    for c in range(len(map_copy[0])):
                        if map_copy[r][c] == i[0]:
                            map_copy[r][c - j[1]] = i[0]
                            map_copy[r][c] = 0
                            for tn in range(len(target_copy)):
                                if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                    target_copy[tn][1] -= j[1]
                # 检查条件：
                # ①是否直接达成目标
                # if check_target(target_copy):
                #     print('已经找到满足条件的解，需要打印')
                #     pass
                #     exit(0)
                # ②不能与历史位置产生重复
                map_copy_s = simp_map(map_copy)
                if check_history(map_copy_s):
                    map_history.append(
                        [current, map_copy, target_copy, map_history[current][3] + 1, map_copy_s,
                         [i[0], direction_dic[j[0]] + str(j[1])]])
            elif j[0] == 4 and j[1] != 0:  # 向右移动
                map_copy = copy.deepcopy(map_history[current][1])
                target_copy = copy.deepcopy(map_history[current][2])
                for r in range(len(map_copy)):
                    for c in range(len(map_copy[0]) - 1, -1, -1):
                        if map_copy[r][c] == i[0]:
                            map_copy[r][c + j[1]] = i[0]
                            map_copy[r][c] = 0
                            for tn in range(len(target_copy)):
                                if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                    target_copy[tn][1] += j[1]
                # 检查条件：
                # ①是否直接达成目标
                # if check_target(target_copy):
                #     print('已经找到满足条件的解，需要打印')
                #     pass
                #     exit(0)
                # ②不能与历史位置产生重复
                map_copy_s = simp_map(map_copy)
                if check_history(map_copy_s):
                    map_history.append(
                        [current, map_copy, target_copy, map_history[current][3] + 1, map_copy_s,
                         [i[0], direction_dic[j[0]] + str(j[1])]])
    current = current + 1

# 求不出解
if current == len(map_history):
    print('无解')
    sys.exit(0)

# 追溯步骤
map_trace = []
while current != -1:
    map_trace.insert(0, map_history[current])
    current = map_history[current][0]

# 打印求解过程程序-打印 MAP 、 移动图形 和 方向、步数
print('\n最短 {} 步\n'.format(len(map_trace) - 1))
for i in map_trace:
    print('第 {} 步：图形 {} 移动 {}'.format(i[3], i[5][0], i[5][1]))
    print_map(i[1])
